# encoding:utf-8

import sys
import datetime

start_time = datetime.datetime.now()

# 在这编辑新图形
# 格式，奇数行列为图形，偶数行列为墙
# 墙：-1没墙，1有墙
# 图形：从2开始编号
m = [[ 2,-1, 3,-1, 0, 1, 0,-1, 0, 1, 0,-1, 0],
     [ 1, 1, 1, 1,-1,-1,-1,-1,-1,-1,-1,-1, 1],
     [ 4,-1, 0,-1, 0, 1, 0, 1, 0,-1, 0,-1, 0],
     [ 1, 1,-1,-1,-1,-1, 1, 1,-1,-1,-1,-1,-1],
     [ 0, 1, 0,-1, 0,-1, 0,-1, 0,-1, 0,-1, 0],
     [-1,-1,-1,-1, 1, 1,-1,-1,-1,-1,-1,-1, 1],
     [ 0, 1, 0, 1, 0, 1, 0,-1, 0, 1, 0, 1, 0],
     [-1,-1, 1, 1,-1,-1,-1,-1,-1,-1, 1, 1,-1],
     [ 0,-1, 0,-1, 0, 1, 0,-1, 0,-1, 0,-1, 0],
     [-1,-1,-1,-1,-1,-1, 1, 1,-1,-1,-1,-1,-1],
     [ 0, 1, 0,-1, 0,-1, 0,-1, 0, 1, 0,-1, 0],
     [ 1, 1,-1,-1,-1,-1, 1, 1, 1, 1, 1, 1,-1],
     [ 0,-1, 0,-1, 0,-1, 0,-1, 0,-1, 0,-1, 0]]

# 在这编辑目标图形
mtarget =   [[ 0,-1, 0,-1, 0, 1, 0,-1, 0, 1, 0,-1, 0],
             [ 1, 1, 1, 1,-1,-1,-1,-1,-1,-1,-1,-1, 1],
             [ 0,-1, 0,-1, 0, 1, 0, 1, 0,-1, 0,-1, 0],
             [ 1, 1,-1,-1,-1,-1, 1, 1,-1,-1,-1,-1,-1],
             [ 3, 1, 0,-1, 0,-1, 0,-1, 0,-1, 0,-1, 0],
             [-1,-1,-1,-1, 1, 1,-1,-1,-1,-1,-1,-1, 1],
             [ 0, 1, 0, 1, 4, 1, 0,-1, 0, 1, 0, 1, 2],
             [-1,-1, 1, 1,-1,-1,-1,-1,-1,-1, 1, 1,-1],
             [ 0,-1, 0,-1, 0, 1, 0,-1, 0,-1, 0,-1, 0],
             [-1,-1,-1,-1,-1,-1, 1, 1,-1,-1,-1,-1,-1],
             [ 0, 1, 0,-1, 0,-1, 0,-1, 0, 1, 0,-1, 0],
             [ 1, 1,-1,-1,-1,-1, 1, 1, 1, 1, 1, 1,-1],
             [ 0,-1, 0,-1, 0,-1, 0,-1, 0,-1, 0,-1, 0]]

tt = []
for i in m:
    for j in i:
        if j > 1:
            tt.append(j)
blocks = tuple(tt)


def gravity(m):
    """重力作用"""
    r = len(m)
    c = len(m[0])
    for c1 in range(c - 1, -1, -2):
        for r1 in range(r - 1, -1, -2):
            if m[r1][c1] in blocks:
                if r1 < r - 1:
                    r2 = r1 + 1
                    while r2 < r and m[r2][c1] < 1:
                        r2 += 1
                    r2 -= 1
                    if m[r2][c1] == -1:
                        r2 -= 1
                    m[r1][c1], m[r2][c1] = m[r2][c1], m[r1][c1]


def print_map(m):
    """打印当前图形"""
    for i in m:
        for j in i:
            print('{:2d}'.format(j), end=' ')
        print()
    print()


def rotate_left(m):
    """向左转-无重力版本"""
    r = len(m)
    c = len(m[0])
    newm = [[0 for x in range(r)] for y in range(c)]
    for i in range(c):
        for j in range(r):
            newm[i][j] = m[j][c - i - 1]
    return newm


def rotate_left_g(m):
    """向左转"""
    r = len(m)
    c = len(m[0])
    newm = [[0 for x in range(r)] for y in range(c)]
    for i in range(c):
        for j in range(r):
            newm[i][j] = m[j][c - i - 1]
    gravity(newm)
    return newm


def rotate_right_g(m):
    """向右转"""
    r = len(m)
    c = len(m[0])
    newm = [[0 for x in range(r)] for y in range(c)]
    for i in range(c):
        for j in range(r):
            newm[i][j] = m[r - j - 1][i]
    gravity(newm)
    return newm


# 广搜数据结构：
# 本级指针(index),[上级指针,map,总步数,旋转方向]

# 广搜思路：
# 1 尝试所有可能移动：左转和右转
# 2 检查是否与历史重复
#       与历史不重复，列表+1
#   2.1 检查是否达成目标
#       达成：结束，回溯指针出解
# 4 尝试下一个

def check_history(m):
    """倒序检查历史"""
    for i in range(len(route) - 1, -1, -1):
        if m == route[i][1]:
            return False
    return True


mtargets = [mtarget]
mtarget = rotate_left(mtarget)
mtargets.append(mtarget)
mtarget = rotate_left(mtarget)
mtargets.append(mtarget)
mtarget = rotate_left(mtarget)
mtargets.append(mtarget)

route = [[-1, m, 0, '']]
current = 0
p_find = False
solution_index = 0
while current < len(route) and not p_find:
    if current % 1000 == 0:
        print('第 {} 次循环，第 {} 步'.format(current, route[current][2]))
    # 尝试左方向
    mnew = rotate_left_g(route[current][1])
    if check_history(mnew):
        route.append([current, mnew, route[current][2] + 1, '左转'])
        if mnew in mtargets:
            p_find = True
            solution_index = len(route) - 1
    # 尝试右方向
    mnew = rotate_right_g(route[current][1])
    if check_history(mnew):
        route.append([current, mnew, route[current][2] + 1, '右转'])
        if mnew in mtargets:
            p_find = True
            solution_index = len(route) -1
    current += 1

if not p_find:
    print('无解')
    sys.exit(0)

so_route = []
while solution_index != -1:
    so_route.insert(0, route[solution_index])
    solution_index = route[solution_index][0]

# 打印求解过程
print('\n最短 {} 步\n'.format(len(so_route) - 1))
for i in so_route:
    print('第 {} 步：{}'.format(i[2], i[3]))
    # print_map(i[1])

end_time = datetime.datetime.now()

print('总耗时： {}'.format(end_time - start_time))
